[% setvar title Arrays: part and flatten %]
<div id="archive-notice">
    <h3>This file is part of the Perl 6 Archive</h3>
    <p>To see what is currently happening visit <a href="http://www.perl6.org/">http://www.perl6.org/</a></p>
</div>
<div class='pod'>
<a name='TITLE'></a><h1>TITLE</h1>
<p>Arrays: part and flatten</p>
<a name='VERSION'></a><h1>VERSION</h1>
<pre>  Maintainer: Jeremy Howard &lt;<a href='mailto:j@howard.fm'>j@howard.fm</a>&gt;
  Date: 10 Aug 2000
  Last Modified: 21 Sep 2000
  Mailing List: <a href='mailto:perl6-language-data@perl.org'>perl6-language-data@perl.org</a>
  Number: 91
  Version: 4
  Status: Frozen</pre>
<a name='DISCUSSION'></a><h1>DISCUSSION</h1>
<p>The discussion points for this RFC were the same as those for RFC 90.</p>
<a name='ABSTRACT'></a><h1>ABSTRACT</h1>
<p>It is proposed that two new functions, <code>part</code> and <code>flatten</code>, be added to
Perl. <code>part($part_size, @list, $skip)</code> would return @list broken into
references to sub-lists, each one $list_size in size, offset from the end
of the previous sub-list by $skip. <code>flatten(@list_of_lists, $nest_level)</code>
would take a list of lists and dereference the elements recursively, up to
$nest_level levels deep. Both functions would return an alias into the
original list, not a copy of the elements.</p>
<a name='CHANGES'></a><h1>CHANGES</h1>
<a name='Since v2'></a><h2>Since v2</h2>
<ul>
<li><a name='Described aliasing behaviour of flatten and part'></a>Described aliasing behaviour of flatten and part</li>
<li><a name='Added flatten builtin'></a>Added <code>flatten</code> builtin</li>
</ul>
<a name='Since v1'></a><h2>Since v1</h2>
<ul>
<li><a name='Moved list to <a href='mailto:perl6-language-data@perl.org'>perl6-language-data@perl.org</a>'></a>Moved list to <a href='mailto:perl6-language-data@perl.org'>perl6-language-data@perl.org</a></li>
<li><a name='Changed name from partition'></a>Changed name from <code>partition</code></li>
<li><a name='Add optional third argument to allow skipping elements'></a>Add optional third argument to allow skipping elements</li>
<li><a name='Make difference between unmerge and part explicit'></a>Make difference between <code>unmerge</code> and <code>part</code> explicit</li>
</ul>
<a name='DESCRIPTION'></a><h1>DESCRIPTION</h1>
<p>In order to work with lists of arbitary size, it is often necessary to
split a list into equal sized sub-lists. A <code>part</code> function is proposed
that achieves this:</p>
<pre>  @list = (1,2,3,4,5,6);
  @parted_list = part(2, @list);   # ([1,2],[3,4],[5,6])</pre>
<p>This is useful to provide tuples to functions that can operate on lists of
lists, for instance:</p>
<pre>  @sum_pairs = map {$_-&gt;[0] + $_-&gt;[1]} @parted_list;   # (3,7,11)</pre>
<p>The optional third argument can be used to skip over elements of the list:</p>
<pre>  @list = (1,2,3,4,5,6,7,8);
  @parted_list = part(2, @list, 1);   # ([1,2],[4,5],[7,8])</pre>
<p>If the list to be parted is not an exact multiple of the part size, the
final list reference is not padded. For example:</p>
<pre>  @list2 = (1..7);
  @parted_list2 = part(3, @list2);   # ([1,2,3], [4,5,6], [7])</pre>
<p>A list that has been parted can be flattened again using the
<code>flatten</code> function:</p>
<pre>  @parted_list2 = ([1,2,3], [4,5,6], [7]);
  @list2 = flatten(@parted_list2);   # (1,2,3,4,5,6,7)</pre>
<p><code>flatten</code> can work on arrays of greater than two dimensions:</p>
<pre>  my @some_LOL = ([[1,2], [3,4]],
                  [[5,6], [7,8]]);
  my @flat_LOL = flatten(@some_LOL);   # ([1,2,3,4], [5,6,7,8])</pre>
<p>The innermost list of lists is flattened first. To flatten more levels of
nesting, use the optional second argument:</p>
<pre>  my @some_LOL = ([[1,2], [3,4]],
                  [[5,6], [7,8]]);
  my @flat_LOL = flatten(@some_LOL,2);   # (1,2,3,4,5,6,7,8)</pre>
<p>Both <code>part</code> and &lt;flatten&gt; do not make a copy of the elements of their
arguments; they simply create an alias to them:</p>
<pre>  @parted_list2 = ([1,2,3], [4,5,6], [7]);
  @list2 = flatten(@parted_list2);   # (1,2,3,4,5,6,7)
  $list2[1] = 0;
  @parted_list2 == ([1,0,3], [4,5,6], [7]);   # True</pre>
<p><code>merge</code> (see RFC 90) and <code>part</code> can work together to allow manipulation
of arbitary sized lists. For instance, we can extend the $sum_xy function
used as an example in the <code>merge</code> RFC, which takes two lists and returns
the sum of them multiplied together component-wise:</p>
<pre>  $sum_xy = sub {reduce ^last+^x*^y, merge($_[0], $_[1])};</pre>
<p>to a function $sum_mult that does the same with an arbitary number of
lists:</p>
<pre>  # Multiply all the elements of a list together, returning the result
  $apply_times = reduce (^total * ^element, @^multiplicands);
  # Swap the rows and columns of a list of lists
  $transpose = part(
    # Find the size of each column
    scalar @^list_of_lists,
    # Interleave the rows
    merge(@^lists_of_lists);
  )

  # Take a list of references to lists, multiply them component-wise,
  #   and return their sum
  $sum_mult = reduce (
    ^total + $apply_times-&gt;( @^next_list ),
    $transpose-&gt;(^list_of_lists),
  );

  # Example usage of $sum_mult
  @a = (1,3,5);
  @b = (2,4,6);
  @c = (-1,1,-1);
  $answer = $sum_mult-&gt;(\@a, \@b, \@c);   # 1*2*-1+3*4*1+5*6*-1 = -20</pre>
<p>A common usage of <code>part</code> and <code>unmerge</code> is to access the rows and columns
of a matrix stored as a flat list:</p>
<pre>  @array = ( a1, a2, a3,
             b1, b2, b3,
             c1, c2, c3 );
  @columns = unmerge(3,@array) # Return the columns
  @rows = part(3,@array)       # Return the rows</pre>
<a name='IMPLEMENTATION'></a><h1>IMPLEMENTATION</h1>
<p>The <code>part</code> functions should be evaluated lazily. Because it is used in
common operations such as the transposition of a matrix, its efficiency is
particularly important.</p>
<p><code>part</code> and <code>flatten</code> return an alias into the original list, not a copy
of the elements.</p>
<p><code>part</code> and <code>flatten</code> are just special cases of <code>reshape</code> (from RFC
148).</p>
<a name='REFERENCES'></a><h1>REFERENCES</h1>
<p>RFC 23: Higher order functions</p>
<p>RFC 76: Builtin: reduce</p>
<p>RFC 90: Builtins: merge() and unmerge()</p>
<p>RFC 148: Add reshape() for multi-dimensional array reshaping</p>
<a name='ACKNOWLEDGEMENTS'></a><h1>ACKNOWLEDGEMENTS</h1>
<p>Damian Conway: Numerous comments on first draft</p>
</div>
